#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define MAX(X,Y)

struct _tree {
	int r;
	struct _tree *L;
	struct _tree *R;
};

void traverse_tree_preorder(struct _tree *);
void traverse_tree_inorder(struct _tree *);
void traverse_tree_reverse_inorder(struct _tree *);
void traverse_tree_postorder(struct _tree *);
void traverse_tree_levelorder(struct _tree *);

void delete_node(struct _tree **, int);

void distroy_tree(struct _tree **);
void insert(struct _tree **, int);

int max(int, int);
int powerof(int, int);
int tree_depth(struct _tree *);

struct _tree * swaptree(struct _tree *);

int
iseven(int x)
{
	if(x/2 == 0)
		return 1;
	else
		return 0;
}

int
powerof(int x, int y)
{
	int i,ans=1;

	if(y == 0) {
		return ans;
	} else {
		for(i=1; i<=y; i++) {
			ans=x*ans;
		}
		return ans;
	}
}

int
max(int x, int y)
{
	if (x > y)
		return x;
	else 
		return y;
}

void
distroy_tree(struct _tree **p)
{
	struct _tree *temp;

	temp=*p;

	if(temp == NULL) {
		return;
	}

	distroy_tree(&(temp->L));
	distroy_tree(&(temp->R));
	
	free(temp);
	temp=NULL;

	*p=temp;
}

void
insert(struct _tree **p, int x)
{	
	struct _tree *temp;

	assert(p);

	temp=*p;

	if(temp == NULL) {
		temp=malloc(sizeof(struct _tree));
		temp->r=x;
		temp->L=temp->R=NULL;	
		*p=temp;
	} else {
		if(temp->r > x) {
			insert(&(temp->L),x);
		} else if(temp->r < x) {
			insert(&(temp->R),x);
		} else {
			printf("\nNumber alreary exist in tree\n");
		}
	}
}

void
delete_node(struct _tree **p, int x)
{
	struct _tree *temp,*tnode,*tpnode;

	temp=*p;

	if( *p!= NULL ) {
		if(temp->r > x) {
			delete_node(&(temp->L),x);
		} else if(temp->r < x) {
			delete_node(&(temp->R),x);
		} else if(temp->r == x) {
			if((temp->L == NULL) && (temp->R == NULL)) {
				*p=NULL;
			} else if((temp->L == NULL) && (temp->R != NULL)) {
				*p=temp->R;
			} else if((temp->L != NULL) && (temp->R == NULL)) {
				*p=temp->L;
			} else if((temp->L != NULL) && (temp->R != NULL)) {
				tpnode=temp;
				tnode=temp->R;
				while(tnode->L != NULL) {
					tpnode=tnode;
					tnode=tnode->L;
				}
				tnode->L=temp->L;
				*p=temp->R;
			} 
			free(temp);
		}
	}
}

struct _tree *
swaptree(struct _tree *p)
{
	struct _tree *lnode,*rnode;
	if( p == NULL ) {
		return p;
	}
	rnode=swaptree(p->L);	
	lnode=swaptree(p->R);	
	p->R=rnode;
	p->L=lnode;
	return p;		
}

void
traverse_tree_preorder(struct _tree *p)
{
	if (p == NULL ) {
		return;
	}
	printf("%d\t",p->r);
	traverse_tree_preorder(p->L);
	traverse_tree_preorder(p->R);
}

void
traverse_tree_inorder(struct _tree *p)
{
	if (p == NULL ) {
		return;
	}
	traverse_tree_inorder(p->L);
	printf("%d\t",p->r);
	traverse_tree_inorder(p->R);
}

void
traverse_tree_reverse_inorder(struct _tree *p)
{
	if (p == NULL ) {
		return;
	}
	traverse_tree_reverse_inorder(p->R);
	printf("%d\t",p->r);
	traverse_tree_reverse_inorder(p->L);
}

void
traverse_tree_postorder(struct _tree *p)
{
	if (p == NULL ) {
		return;
	}
	traverse_tree_postorder(p->L);
	traverse_tree_postorder(p->R);
	printf("%d\t",p->r);
}

int
tree_depth(struct _tree *p)
{
	int count=0;
	if (p != NULL) {
		count=count+1;
		count=max(count+tree_depth(p->L),count+tree_depth(p->R));
	}

	return count;
}

void
printVertical(struct _tree *p, int *row)
{
	if (p != NULL){
		(*row)++;
		printVertical(p->R,row);
		int i;
	
		if(p->R != NULL) {
			for(i=0;i<(3*(*row));i++) {
				printf(" ");
			}
			printf(" /\n");
		}
		for(i=0;i<(3*(*row));i++) {
			printf(" ");
		}
		printf("%d\n", p->r);

		if(p->L != NULL) {
			for(i=0;i<(3*(*row));i++) {
				printf(" ");
			}
			printf(" \\\n");
		}
		printVertical(p->L,row);
		(*row)--;
	}
}

void
printTreeLines(struct _tree *p) 
{
	int row = 0;
	printVertical(p,&row);
}

void
printTree(struct _tree *p,int x,int y)
{
	int i,spaces;

	spaces=2*(powerof(2,y-1));

	if(p == NULL) {
		for(i=0; i<spaces; i++) {
				printf("  ");
		}
		return;
	}

	if(x == 1) {
		for(i=0; i<spaces; i++) {
			if(i == (spaces/2)) {
				printf("%02d",p->r);
			} else {
				printf("  ");
			}
		}
	} else {
		printTree(p->L,x-1,y);
		printTree(p->R,x-1,y);
	}
}

void
traverse_level(struct _tree *p,int x)
{
	if(p == NULL) {
		return;
	}

	if(x==1) {
		printf("%2d",p->r);
	} else {
		traverse_level(p->L,x-1);
		traverse_level(p->R,x-1);
	}
}

void
traverse_tree_levelorder(struct _tree *p)
{
	int i,j,k,d,h=0,w=0;
	d=tree_depth(p);

	for(i=d;i>0;i--) {
		h=h+(powerof(2,i-1));
	}
	
	w=powerof(2,d-1)+(d-1);

	for(i=0;i<d;i++) {
		j=d-i;
		printTree(p,i+1,j);
		for(k=0;k<(powerof(2,j-1));k++) {
			printf("\n");
		}
	}
}

int main()
{
	int val,depth,delnode,choice;
	struct _tree *base;

	base=NULL;

	while(!0) {
		printf("\nMenu Selection\n\n");
		printf("  1. Add node to the tree\n");
		printf("  2. Delete node from the tree\n");
		printf("  3. Display tree in preorder\n");
		printf("  4. Display tree in inorder\n");
		printf("  5. Display tree in postorder\n");
		printf("  6. Display tree in reverse inorder\n");
		printf("  7. Display tree in levelorder (Tree View)\n");
		printf("  8. Distroy tree\n");
		printf("  9. Find the depth of tree\n");
		printf("  0. Exit\n");

		printf("\nEnter your choice (0 to exit): ");
		scanf("%d",&choice);

		switch(choice)	{
			case 0:
				distroy_tree(&base);
				exit(0);
				break;
			case 1:
				printf("\nEnter number to add: ");
				scanf("%d",&val);

				insert(&base,val);

				break;
			case 2:
				printf("\nEnter number to remove from tree: ");
				scanf("%d",&delnode);

				delete_node(&base,delnode);
				//traverse_tree_inorder(base); 
				traverse_tree_levelorder(base);
				printf("\n");

				break;
			case 3:
				printf("\nTree in preorder\n");
				traverse_tree_preorder(base);
				printf("\n");

				break;
			case 4:
				printf("\nTree in inorder(Sorted)\n");
				traverse_tree_inorder(base);
				printf("\n");

				break;
			case 5:
				printf("\nTree in postorder\n");
				traverse_tree_postorder(base);
				printf("\n");

				break;
			case 6:
				printf("\nTree in reverse inorder(Sorted in reverse)\n");
				traverse_tree_reverse_inorder(base);
				printf("\n");

				break;
			case 7:
				printf("\nTree in levelorder\n");
				traverse_tree_levelorder(base);
				//printTreeLines(base);
				printf("\n");

				break;
			case 8:
				printf("\nTree after released from memory\n");
				distroy_tree(&base);
				traverse_tree_inorder(base); 
				printf("\n");
			case 9:
				printf("\nTree depth: ");
				depth=tree_depth(base);
				printf("%d\n",depth);
				printf("\n");

				break;
			default:
				printf("\n\nInvalid choice\n\n");
				break;
		}
	}

	return 0;
}
